package com.yeung.swordoffer;

import java.util.Arrays;

public class 机器人的运动范围 {
    public static void main(String[] args) {
        System.out.println(movingCount(5, 10, 10));//21
    }

    /**
     * 利用回溯法
     *
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public static int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0) return 0;
        //记录格子是否被访问过
        boolean visited[] = new boolean[rows * cols];
        Arrays.fill(visited, false);
        return MovingCountCore(rows, cols, 0, 0, threshold, visited);

    }

    public static int MovingCountCore(int rows, int cols, int row, int col, int threshold, boolean[] visited) {
        int count = 0;
        if (enable(rows, cols, row, col, threshold, visited)) {
            count++;
            visited[row * cols + col] = true;
            count += MovingCountCore(rows, cols, row - 1, col, threshold, visited);//上方的格子
            count += MovingCountCore(rows, cols, row, col - 1, threshold, visited);//左方的格子
            count += MovingCountCore(rows, cols, row + 1, col, threshold, visited);//下方的格子
            count += MovingCountCore(rows, cols, row, col + 1, threshold, visited);//右方的格子
        }
        return count;
    }

    /**
     * 检查是否能够进入某个格子
     *
     * @param row
     * @param col
     * @param rows
     * @param cols
     * @param threshold
     * @param visited   这个格子是否被访问过, 利用一个一维数组来存二维数组
     * @return
     */
    public static boolean enable(int rows, int cols, int row, int col, int threshold, boolean[] visited) {
        if (row >= 0 && row < rows && col >= 0 && col < cols &&
                (getDigitalSum(row, col)) <= threshold && !visited[row * cols + col])
            return true;
        else
            return false;
    }

    /**
     * 计算一个数字的位和
     *
     * @param row
     * @param col
     * @return
     */
    public static int getDigitalSum(int row, int col) {
        int sum = 0;
        while (row > 0) {
            sum += row % 10;
            row /= 10;
        }
        while (col > 0) {
            sum += col % 10;
            col /= 10;
        }

        return sum;
    }
}
